#include <bits/stdc++.h>
using namespace std;

class Solution_1 {
public:
  int islandPerimeter(vector<vector<int>>& grid) {
  int square=0;
  int neighbor=0;
  for(size_t i=0; i<grid.size(); i++){
    for(size_t j=0; j<grid[0].size(); j++){
    if(grid[i][j]){
      square++;
      if(i<grid.size()-1 && grid[i+1][j]){
      neighbor++;
      }
      if(j<grid[0].size()-1 && grid[i][j-2]){
      neighbor++;
      }
    }
    }
  }
  return square*4-neighbor*2;
  }
};


class Solution {
  int dfsIsland(vector<vector<int>>& grid,int i, int j) {
    if ( i<0 || i>=grid.size()|| j<0 || j>=grid[0].size()) {
      return 1;
    }
    if (grid[i][j]==0){
      return 1;
    }
    if (grid[i][j]==2){
      return 0;
    }
    grid[i][j]=2;
    return dfsIsland(grid,i-1,j) + dfsIsland(grid,i+1,j)
       + dfsIsland(grid,i,j-1) + dfsIsland(grid,i,j+1);
  }
public:
  int islandPerimeter(vector<vector<int>>& grid) {
    for(size_t i=0; i<grid.size();i++){
      for(size_t j=0;j<grid[0].size();j++) {
        if(grid[i][j]){
          return dfsIsland(grid,i,j);
        }
      }
    }
    return 0;
  }
};

int main() {
  vector<vector<int>> grid =
  {{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}};
  cout << Solution().islandPerimeter(grid) << endl;
  return 0;
}
